class Solution:
    def maximalRectangle(self, matrix: list) -> int:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        for index, strs in enumerate(matrix[0]):
            matrix[0][index] = int(strs)
        for i in range(1, len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == "1":
                    matrix[i][j] = int(matrix[i-1][j]) + 1
                else:
                    matrix[i][j] = 0
        res = 0
        for lists in matrix:
            res = max(res, self.largestRectangleArea(lists))
        return res

    def largestRectangleArea(self, heights: list) -> int:
        up_zhan, res = [[0, 0], ], 0
        heights.append(0)
        for index, num in enumerate(heights):
            while num < up_zhan[-1][1]:
                mid_num = up_zhan.pop(-1)
                res = max(res, mid_num[1] * (index - up_zhan[-1][0]))
            up_zhan.append([index + 1, num])
        return res


a = Solution()
print(a.maximalRectangle([["1", "0", "1", "0", "0"],
                          ["1", "0", "1", "1", "1"],
                          ["1", "1", "1", "1", "1"],
                          ["1", "0", "0", "1", "0"]]))